package stu.day1_day8;

public class LeetCode877 {
    public boolean stoneGame(int[] piles) {
        int n=piles.length;
        int [][]dp=new int[n][n];
        //初始化dp[i][i]
        for(int i=0;i<n;i++)
            dp[i][i]=piles[i];

        //注意这里的两个循环
        //第一个循环dis代表间隔距离，比如说dis=1时，配合接下来i的循环，
        //会不断得到相邻2个石头堆的最优选择策略，比如说{1,2,3,4时}，会
        //得到{1,2}、{2、3}、{3、4}的最优选择策略；当dis=2时，会得到相
        //邻3个石头堆的最优选择策略，得到{1,2,3}、{2、3、4}。
        for(int dis=1;dis<n;dis++)
            for(int i=0;i<n-dis;i++)//i仍然表示起始位置
                dp[i][i+dis]=Math.max(piles[i]-dp[i+1][i+dis],piles[i+dis]-dp[i][i+dis-1]);
        return dp[0][n-1]>0;

    }

    public static void main(String[] args) {

    }
}
